Triangle meshes have become the most common representation for complex surfaces. Most three dimensional objects available on the internet are supplied in a format which is based on triangle meshes or polygonal meshes, which can easily transformed into triangle meshes. Especially, in the domain of the internet storage space efficient representations of triangle meshes are important. Therefore a wide variety of compression algorithms are available.
3D-hardware support is primarily based on the rendering of triangles. Each triangle is specified by its three vertices, where each vertex contains three coordinates, possibly the surface normal, material attributes and/or texture coordinates. The coordinates and normals are specified with floating point values, such that a vertex may contain data of up to 36 bytes. Thus the transmission of a vertex is expensive and the simple approach of specifying each triangle by the data of its three vertices is wasteful as for an average triangle mesh each vertex must be transmitted six times.
The introduction of triangle strips helped to save unnecessary transmission of vertices. Two successive triangles in a triangle strip join an edge. Therefore, from the second triangle on, the vertices of the previous triangle can be combined with only one new vertex to form the next triangle. As with each triangle at least one vertex is transmitted and as an average triangle mesh has twice as many triangles as vertices, the maximal gain is that each vertex has to be transmitted only about two times. Two kinds of triangle strips are commonly usedxe2x80x94the sequential and the generalized triangle strips. In generalized triangle strips an additional bit is sent with each vertex to specify to which of the free edges of the previous triangle the new vertex is attached. Sequential strips even drop this bit and impose that the triangles are attached alternating.
It is an object of this invention to propose a method for compressing and decompressing large geometric data sets which is fast and simple.
The method of the invention compresses triangle meshes which consist of a list of vertices and a list of triangles, each triangle containing the three vertex indices and the indices of the three edge-adjacent triangles. If the latter adjacency information is not known it can be easily computed through hashing.
The invention is based on a region growing traversal of the triangle mesh starting for each edge-connected component with an arbitrary triangle of this component. The border of the growing region is called the cut-border. It divides the mesh into the inner and the outer part, which contain the already compressed and the remaining triangles respectively.
Triangles are added to the inner part at a distinguished current cut-border edge which will be called the gate. After each addition of a triangle the gate moves on to another cut-border edge, until all triangles of an edge-connected component of the triangle mesh have been compressed. This is done for each edge-connected component.
The compressed representation contains for each triangle a bit code of an operation identifier which tells how the triangle was formed upon the gate. There are three cases: the gate is an edge of the mesh border, the gate forms a triangle with a vertex on the cut-border or the triangle is formed with a new vertex. The different operations are called xe2x80x9cborderxe2x80x9d, xe2x80x9cnew vertexxe2x80x9d and xe2x80x9cconnectxe2x80x9d. The xe2x80x9cconnectxe2x80x9d operations take one parameter which specifies the offset of the third vertex relative to the gate. The xe2x80x9cconnectxe2x80x9d operations with offset one and minus one are also called xe2x80x9cconnect forwardxe2x80x9d and xe2x80x9cconnect backwardxe2x80x9d. All other xe2x80x9cconnectxe2x80x9d operations split the cut-border into two loops. As the triangle meshes describe two dimensional surfaces in three dimensional space, two cut border loops can grow together again, actually once for each handle of the triangle mesh. The operation which unifies two loops is called xe2x80x9cunionxe2x80x9d and takes two parameters, the index of the second loop and the offset of the third triangle vertex within this loop.
The cut-border data structure basically consists of a stack of doubly linked lists containing the verticesxe2x80x94or their indicesxe2x80x94, which are adjacent to triangles of the inner and the outer part at the same time.
Data at the faces, edges or vertices such as their coordinates are included in the compressed representation each time a new mesh element is added to the cut-borderxe2x80x94for example the vertex coordinates of vertex v[i] are encoded after the xe2x80x9cnew vertexxe2x80x9d operation which introduces v[i] into the cut-border.
The decompression algorithm builds the mesh in the same order as the compression algorithm traverses the original mesh. With the help of the indices attached to the xe2x80x9cconnectxe2x80x9d operations the original connectivity can be reconstructed with permuted vertices and triangles. During decompression the edge adjacency information can be reconstructed with no additional cost.